//题目：
//给定数组nums1，nums2，找出两个数组之间的公共元素
// 1 < nums1.length, nums2.length < 1000
// 1 < nums1[i], nums2[i] < 10000

#include <iostream>
#include <vector>
using namespace std;

// version 1 自己写的
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums1 int整型vector
     * @param nums2 int整型vector
     * @return int整型vector
     */
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector<int> ret, hash1(1001), hash2(1001);
        int i = 0, n = nums1.size(), m = nums2.size();
        int nmax = -1, mmax = -1;
        while (i < m + n) {
            if (i < n) {
                hash1[nums1[i]]++;
                if (nums1[i] > nmax) nmax = nums1[i];
            }
            else {
                hash2[nums2[i - n]]++;
                if (nums2[i - n] > mmax) mmax = nums2[i - n];
            }
            ++i;
        }


        //此时两个数组的情况就统计在了两个哈希数组内
        int end = min(mmax, nmax);
        for (int i = 1; i <= end; ++i) {
            if (hash1[i] && hash2[i]) ret.push_back(i);
        }
        return ret;
    }
};


//这里还是投机取巧 发现数组大小不超过1000，数字大小1~10000
//直接拿两个哈希表统计了！


//version 2 其实可以只拿一个哈希表来做(视频答案写的！)
class Solution2 {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums1 int整型vector
     * @param nums2 int整型vector
     * @return int整型vector
     */
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        //1.统计一个数组到哈希
        vector<int> ret, hash(1000);
        for(auto x : nums1) hash[x]++;

        //2.遍历另一个数组，查找数字是否在哈希内，如果有的话，那就加入到ret上！
        for(int i = 0; i < nums2.size(); ++i){
            int num = nums2[i];
            if(hash[num]) {
                ret.push_back(num);
                hash[num] = 0; 
            }
        }
        //注意，这里如果出现了多个一样的数字是重复的，要去重！ 所以，我们遍历到存在哈希表后，把这个位置主动置0！(删除)
        return ret;
    }
};